package com.mj.listen2._01_排序.cmp;

/**
 * 堆排序
 */
public class _03_HeapSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        // 批量建立大根堆
        int heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            // 自下而上的下滤
            shiftDown(i, heapSize);
        }

        // 堆排序思想:
        while (heapSize > 1) {
            // 交换堆顶元素和尾部元素
            swap(0, heapSize - 1);
            // 因为最后已经是最大值了，所以下一次就不去做比较了
            heapSize--;
            // 从0开始进行下滤
            shiftDown(0, heapSize);
        }
    }

    // 从 index 索引位置开始进行下滤操作
    private void shiftDown(int index, int heapSize) {
        // 拿这个值往下比较
        T element = array[index];
        // 非叶子节点的数量: 公式:floor (n / 2)。最后一个非叶子节点的索引：index = size >> 1 - 1; 第一个叶子节点的索引 size >> 1
        int notLeafCount = heapSize >> 1;
        while (index < notLeafCount) {
            // 默认左侧孩子为最大
            int childIndex = (index << 1) + 1;
            T child = array[childIndex];

            // 与右侧的比较
            // 右孩子的索引
            int childRightIndex = childIndex + 1;
            // childRightIndex < size 表示有右孩子
            if (childRightIndex < heapSize && cmp(array[childRightIndex], child) > 0) {
                // 右孩子大
                childIndex = childRightIndex;
                child = array[childRightIndex];
            }

            // 是否比父节点大
            if (cmp(element, child) >= 0) break;

            // 说明孩子比较大
            // 把孩子值赋值给index父节点索引位置
            array[index] = child;
            // 更新index指针，指向子节点位置
            index = childIndex;
        }
        // 把element放置到对应的位置
        array[index] = element;
    }
}
